<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>斐波那契数列</title>
</head>

<body>
    <script>

        // 1 1 2 3 5 8 13

        // 一 递归 复杂度 O(2的n次方)
        function fb (n) {
            if (n === 1 || n === 2) {
                return 1
            }
            return fb(n - 1) + fb(n - 2)
        }

        // console.log(fb(1))
        // console.log(fb(2))
        // console.log(fb(3))
        // console.log(fb(4))
        // console.log(fb(5))


        // 二 for循环 复杂度 O(n)
        function fb2 (n) {
            var current = 1,
                next = 1,
                sum = 0

            for (var i = 0; i < n; i++) {
                sum = current + next
                current = next
                next = sum
            }
            return current
        }

        // console.log(fb2(0))
        // console.log(fb2(1))
        // console.log(fb2(2))
        // console.log(fb2(3))
        // console.log(fb2(4))
        // console.log(fb2(5))


        // 三 尾递归 (函数的最后是函数调用)  复杂度 O(n)
        function fb3 (n, current = 1, next = 1) {
            if (n <= 1) {
                return next
            }

            return fb3(n - 1, next, current + next)
        }

        console.log(fb3(0))
        console.log(fb3(1))
        console.log(fb3(2))
        console.log(fb3(3))
        console.log(fb3(4))
        console.log(fb3(5))

        // 四 字典 复杂度 O(n)
        function fb4(n) {
            if(n in dict) {
                return dict[n]
            } else {
                let ans = fb4(n-1) + fb4(n-2)
                dict[n] = ans
                return ans
            }
        }

        let dict = {1: 1, 2: 1}
        console.log(fb4(1))
        console.log(fb4(2))
        console.log(fb4(3))
        console.log(fb4(4))
        console.log(fb4(5))
        console.log(dict)

        // 五 生成器 复杂度 O(n)
        function* fb5() {
            let fibn_1 = 1
            let fibn_2 = 1
            while (true){
                let next = fibn_1 + fibn_2
                yield next
                fibn_1 = fibn_2
                fibn_2 = next
            }
        }

        let fib = fb5()
        console.log(fib.next())
        console.log(fib.next())
        console.log(fib.next())
        console.log(fib.next())

        for (i of fib) {
            console.log(i)
        }

    </script>
</body>

</html>